/**
 * 题目描述： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。给定 n 是一个正整数
 *
 * 思路1： 递归，f(n) = f(n-1) + f(n-2)
 */

/**
 * @param {number} n
 * @return {number}
 */
// 定义记忆数组 f
const f = [];
const climbStairs = function (n) {
  if (n == 1) {
    return 1;
  }
  if (n == 2) {
    return 2;
  }
  // 若f[n]不存在，则进行计算
  if (f[n] === undefined) f[n] = climbStairs(n - 1) + climbStairs(n - 2);
  // 若f[n]已经求解过，直接返回
  return f[n];
};

console.log(climbStairs(3));

/**
 * 动态规划方式解法：
 * 1. 最优子结构，最优解包含子问题的最优解,状态转移方程
 * 2. 重叠子问题，在递归的过程中，出现反复计算的情况
 */

const climbStairs2 = function (n) {
  // 初始化状态数组
  const f = [];
  // 初始化已知值
  f[1] = 1;
  f[2] = 2;
  // 动态更新每一层楼梯对应的结果
  for (let i = 3; i <= n; i++) {
    f[i] = f[i - 2] + f[i - 1];
  }
  // 返回目标值
  return f[n];
};
